package com.likou;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

public class q144 {

    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        TreeNode p = root;
        Deque<TreeNode> deque = new LinkedList<>();
        while (p != null || !deque.isEmpty()) {
            while (p != null) {
                deque.push(p);
                ans.add(p.val);
                p = p.left;
            }

            TreeNode pop = deque.pop();
            p = pop.right;
        }

        return ans;
    }

//    public List<Integer> preorderTraversal(TreeNode root) {
//        List<Integer> ans = new ArrayList<>();
//        TreeNode p = root;
//        preorder(p, ans);
//
//        return ans;
//    }
//
//    private void preorder(TreeNode p, List<Integer> list) {
//        if (p == null) {
//            return;
//        }
//        list.add(p.val);
//        preorder(p.left, list);
//        preorder(p.right, list);
//    }
}
